"""
算法简介

算法 + 数据结构 = 程序

算法是一组完成任务的指令。

常见的6种大O运行时间：
    1.O(log n)，对数时间。(如二分查找算法)
    2.O(n)，线性时间。(如简单查找算法)
    3.O(n * log n)，介于线性和平方之间的时间。(如快速排序算法)
    4.O(n2)，平方时间。(如选择排序算法)
    5.O(n!)，阶乘时间。(如旅行商问题算法)
    6.O(1)，常数时间。

小结：
    1.二分查找的速度比简单查找快得多。
    2.O(log n)比O(n)快，需要搜索的元素越多，前者比后者就快得越多。
    3.算法运行时间并不以秒为单位。
    4.算法运行时间是从其增速的角度度量的。
    5.算法运行时间用大O表示法表示。
"""


def simple_search(item_list, item):
    """
    简单查找
    """
    for num in item_list:
        if num == item:
            return item_list.index(item)

    return None


def binary_search(item_list, item):
    """
    二分查找
    边界：仅当列表是有序的时候，二分查找才管用。
    """

    low = 0
    high = len(item_list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = item_list[mid]

        if guess == item:
            return mid

        if guess > item:
            high = mid - 1
        else:
            low = mid + 1

    return None


if __name__ == "__main__":
    # 生成有序列表
    items = [i for i in range(1, 100)]

    # 简单查找
    print(simple_search(items, 50))
    print(simple_search(items, 101))

    # 二分查找
    print(binary_search(items, 50))
    print(binary_search(items, 101))
